COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	TITLE PAGE - 1.						   JUNE 1974.
C00004 00003		CONTENTS:
C00005 00004	TITLE PAGE - 2.						   JUNE 1974.
C00008 00005	DETAILED TABLE OF CONTENTS.
C00010 00006	1.0 INTRODUCTION.
C00017 ENDMK
C⊗;
TITLE PAGE - 1.						   JUNE 1974.
{draft - draft - draft - draft - draft - draft - draft - draft - draft}
{The portions of text embedded in curly brakets are draft nodes which
will not appear in the final document.}


               GEOMETRIC MODELING FOR COMPUTER VISION.


                          BRUCE G. BAUMGART


ABSTRACT:

	This thesis is about a computer graphics approach to computer
vision.  The main  idea is that a 3-D geometric model of the physical
world is an expedient bridge between image processing  and artificial
intelligence;  this idea is developed into a system consisting of two
programs  named GEOMED and  CRE.   The system is  demonstrated in the
context of viewing objects on a turntable.



---------------------------------------------------------------------
This  research  was  supported  in  part  by  the  Advanced  Research
Projects  Agency of  the  Office of  the Secretary  of  Defense under
Contract No. SD-183.

The views and  conclusions contained  in this document  are those  of
the author and should not  be interpreted as necessarily representing
the  official policies, either expressed or  implied, of the Advanced
Research Project Agency or the United States Government.
	CONTENTS:

{INTRO}			INTRODUCTION.
{GEM}		1.	GEOMETRIC MODELING THEORY.
{WINGED}	2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.
{GEOMED}	3.	GEOMED AS A 3-D GEOMETRIC MODELING COMMAND LANGUAGE.
{BIN}		4.	A POLYHEDRON INTERSECTION ALGORITHM.
{OCCULT}	5.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{CNTOUR}	6.	VIDEO IMAGE CONTOURING.
{CMPARE}	7.	IMAGE COMPARING.
{CAMERA}	8.	CAMERA SOLVING.
{VIS}		9.	COMPUTER VISION THEORY.
{CONCLU}	10.	CONCLUSION.

	APPENDICES:

{REF}			REFERENCES.
{GNODES}		GEOMED NODE FORMATS.
{CNODES}		CRE NOOE FORMATS.
TITLE PAGE - 2.						   JUNE 1974.

               GEOMETRIC MODELING FOR COMPUTER VISION.


---------------------------------------------------------------------
                           A DISSERTATION

           SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE

                AND THE COMMITTEE ON GRADUATE STUDIES

                       OF STANFORD UNIVERSITY

             IN PARTIAL FULFILLMENT OF THE REQUIREMENTS

                          FOR THE DEGREE OF

                        DOCTOR OF PHILOSOPHY

---------------------------------------------------------------------
                                 BY
                          BRUCE G. BAUMGART
                             JUNE  1974
---------------------------------------------------------------------
DETAILED TABLE OF CONTENTS.

LIST OF BOXES.

LIST OF FIGURES.

ACKNOWLEDGEMENTS

Thesis Adviser:

	John Mc Carthy

Readers:

	Jerome A. Feldman
	Donald E. Knuth
	Alan C. Kay

Good people:

	Jerry	Agin,
	Leona 	Baumgart,
	Tom 	Binford, 
	Jack 	Buchanan,
	Les 	Earnest,
	Tom 	Gafford,
	Steve 	Gibson,
	Ralph 	Gorin,
	Tovar 	Mock,
	Andy 	Moorer,
	Hans 	Moravec,
	Richard	Orban,
	Ted 	Panofsky,
	Lou 	Paul,
	Lynn 	Quam,
	Jeff 	Raskin,
	Ron 	Rivest,
	Irwin	Sobel,
	Robert 	Sproull,
	Ivan 	Sutherland,
	Dan 	Swinehart,
	Russel 	Taylor,
	Marty	Tenenbaum,
	Arthur 	Thomas,
1.0 INTRODUCTION.

	A computer  graphics approach  to computer vision  involves
using  a 3-D geometric  world model to  bridge the  gap between image
processing  and  artificial  intelligence.    Such  geometric  models
provide a  goal for image  analysis,   an origin for  image synthesis
(for  verification),    and  a  data  structure  for spatial  problem
solving. The chapters of this thesis proceed from geometric theory,
through computer implementation of a geometric modeling system,
followed by a contours application to computer vision 

	The theory consists of two essays: chapter 9 is an
essay on vision and chapter 2 is an essay on geometric modeling.
The
vision theory presented is speculative and much  larger in scope than
the  results;  so although  the  vision theory  guided the
design of programs and applications, I do not wish to claim  that the
vision  demonstrated  comes  close  to confirming  the  theory.    In
particular, if the reader skips chapter 9, the rest of the thesis can
be viewed as a discussion of a 3-D drawing  program for automatically
generating  and altering  polyhedral scene  descriptions by  means of
video input.

	The computer implementation consists of
two computer programs  named CRE and  GEOMED.
CRE is  a solution  to the  problem of  finding intensity
contours  in  a  sequence  of  television  pictures  and  of  linking
corresponding contours from  one picture to the next.  The process is
automatic  and is  intended to run  without human  intervention.  The
image sequence output  of CRE is  input to GEOMED,  a package of  3-D
modeling  routines.   In GEOMED,   the  perceived CRE  images  may be
compared with predicted images computed by a hidden line  eliminator;
the perceived images  may be used  to generate new  polyhedral object
descriptions;  or the  images may  be  used to  solve for  the camera
locus.

	The programming discussion is broken into three parts: memory,
process and control in chapters four,  five and six respectively.  In
the  memory chapter,   a small  number of entities  are introduced as
atoms,  a  node representation for each  atom is explained,   and the
assembly of  atoms to represent  further entities is  begun.  Chapter
five, on process, explains  the bulk of the  work, which has been  to
develope a system of  routines that do geometric modeling.   Although
most of the techniques discussed in chapter five have been identified
as relevant  to computer  vision, collecting  them  into a  menagerie
bears upon how  such a system is to be  integrated. Finally,  chapter
six explains the command languages which define the interface between
the modeling system and  its application.  The command  languages are
notable more  for concise and comprehensive notation  rather than for
human engineering; and so must be viewed as low level.

	In Part III, the machinery of part II is applied to a  number
of  vision  and  model  related  problems.    The  main  experimental
demonstration   being  the  automatic  acquistion   of  a  polyhedral
description of  objects rotated on  a turntable  before a  television
camera under conventional lighting.